package com.base.dp;

public class MinFallingPathSum {
    public static void main(String[] args) {
        MinFallingPathSum minFallingPathSum = new MinFallingPathSum();
        System.out.println(minFallingPathSum.minFallingPathSum(new int[][]{{2, 1, 3}, {6, 5, 4}, {7, 8, 9}}));
    }

    private int minFallingPathSum(int[][] matrix) {
        // 1 2
        // 3 4
        // 定义 dp[i][j] 表示从第0行到第i行的最小路径和
        int[][] dp = new int[matrix.length][matrix[0].length];
        dp[0][0] = matrix[0][0];
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                // 第一行
                if (i == 0) {
                    dp[i][j] = matrix[i][j];
                } else {
                    if (j == 0) {
                        // 第一列的值等于上一行同一列和第二列的最小值
                        dp[i][j] = matrix[i][j] + Math.min(dp[i - 1][j], dp[i - 1][j + 1]);
                    } else if (j == matrix[i].length - 1) {
                        //最后一列的值等于上一行同一列和上一列的最小值
                        dp[i][j] = matrix[i][j] + Math.min(dp[i - 1][j], dp[i - 1][j - 1]);
                    } else {
                        // 其他列的值等于上一行同一列和上一行前面一列和上一行后面一列的最小值
                        dp[i][j] = matrix[i][j] + Math.min(Math.min(dp[i - 1][j], dp[i - 1][j - 1]), dp[i - 1][j + 1]);
                    }
                    if (i == matrix.length - 1){
                        min = Math.min(dp[i][j], min);
                    }
                }
            }
        }

        return min;
    }
}
